Міністерство освіти і науки, молоді та спорту України Національний університет «Львівська політехніка» Інститут дистанційного навчання Кафедра СКС
КУРСОВА РОБОТА з дисципліни «Програмування» на тему «Структури даних: однозв’язні списки» Варіант № 12 Завдання на курсову роботу: Реалізувати метод сортування двохшляхового злиття послідовності, яка представлена у вигляді лінійного однозв’язного списку, елементи якого містять по декілька інформаційних полів, одне з яких є ключовим , і всі зміни положення елементів в послідовності виконуються не перестановкою самих елементів, а перестановкою їх зв'язків. Намалювати схему алгоритму для конкретного прикладу послідовності з десяти цілих чисел зі знаком. Дослідити метод на стійкість. Дослідити ефективність метода. Дослідити метод на економність використання пам'яті. Дослідити метод на можливу специфіку вхідної послідовності. Змоделювати фабрику, що виробляє вироби з менших вузлів. Назвемо елементарною деталлю такий вузол, що не складається з дрібніших вузлів. Написати програму, що зчитує набір рядків, які містять чотирьох символьні номери деталей. Перший такий номер у рядку означає неелементарну деталь, а решта чисел означають деталі, з яких складається ця неелементарна деталь. Ці складові деталі можуть бути елементарними, а можуть складатися з інших частин (у такому випадку їх номери з’являться першим номером у якомусь іншому рядку). Програма складає список з елементом заголовку для кожної неелементарної деталі. Заголовок містить назву неелементарної деталі і вказівник на список елементів, що описує її складові частини вказівники на заголовки списків послідовно записуються в список. Для описаного представлення написати програму: а) роздруку всіх неелементарних деталей. б) виведення для кожної неелементарної деталі списку всі елементарні деталей з яких вона складається.  ЗМІСТ ВСТУП………………………………………………………………………. 4  1. СТАТИЧНА СТРУКТУРА…………………………………………… 5  1.1 Синтаксичний аналізатор, що працює зі змінними…………………... 5  1.2 Тестування для наступних значень змінних………………………….. 7  2. СОРТУВАННЯ З РОЗДІЛЕННЯМ…………………………………. 8  2.1 Ідея алгоритму………………………………………………………….. 10   2.1.1 Псевдокод алгоритму…………………………………………….. 10  2.2 Виконання алгоритму…………………………………………………... 11  3. СПИСКИ……………………………………………………………….. 16  3.1 Поняття про однонапрямлені однозв’язні списки……………………. 16  3.2 Робота з однозв'язними списками……………………………………… 17  3.3 Додавання елемента на початок списку……………………………….. 17  3.4 Додавання елемента в кінець списку………………………………….. 19  4. ОРГАНІЗАЦІЯ ОДНОЗВ’ЯЗНИХ СПИСКІВ……………………... 21  4.1 Операція виділення елемента структури через вказівник……………. 21  4.2 Постановка завдання……………………………………………………. 21  4.3 Опис програми………………………………………………………….. 22  4.4 Текст програми………………………………………………………….. 24  4.5 Результати виконання програми………………………………………. 26  ВИСНОВКИ…………………………………………………………………. 27  СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ…………………………….. 28   ВСТУП За допомогою обчислень комп'ютер здатний обробляти інформацію по наперед певному алгоритму. Крім того, комп'ютер за допомогою програмного забезпечення здатний приймати, зберігати і здійснювати пошук інформації, виводити інформацію на різні види пристроїв висновку. Свою назву комп'ютери одержали по своїй основній функції — проведенню обчислень. В даний час функція обчислень для комп'ютерів стає другорядною, і більшість комп'ютерів використовуються для обробки і управління інформацією, а також ігор. Виконання поставлених перед ним завдань комп'ютер може забезпечувати за допомогою переміщення яких-небудь механічних частин, рухи потоків електронів, фотонів, квантових частинок або за рахунок використання ефектів від будь-яких інших добре вивчених фізичних явищ. Термін «комп'ютер» є синонімом абревіатури «ЕОМ» (електронної обчислювальної машини). Після появи персональних комп'ютерів (від англ. personal computer, PC), термін ЕОМ згодом практично ви...